package com.LeeCode;

import java.util.HashMap;
import java.util.Map;


/**
 * 美观的花束
 */

public class CodeLCP068 {
    public static void main(String[] args) {
        int[] flowers = {5,3,3,3};
        int cnt = 2;
        System.out.println(new CodeLCP068().beautifulBouquet(flowers, cnt));
    }

    public int beautifulBouquet(int[] flowers, int cnt) {
        int MOD = 1_000_000_007;
        Map<Integer, Integer> map = new HashMap<>();
        long ans = 0;
        int left = 0;

        for (int right = 0; right < flowers.length; right++) {
            map.merge(flowers[right], 1, Integer::sum);

            while (map.get(flowers[right]) > cnt) {
                map.merge(flowers[left], -1, Integer::sum);
                if (map.get(flowers[left]) == 0) {
                    map.remove(flowers[left]);
                }
                left++;
            }
            ans = (ans + right - left + 1) % MOD;
        }
        return (int) ans;
    }
}
